This invention relates generally to detecting errors in coded bit strings.
Data storage systems, such as disk drives, are prone to various errors that can corrupt data. For example, media and electronic noise can change the content of a magnetic disk, and thereby produce an error. Such errors are not unique to data storage systems. Rather, any system that stores, retrieves, and/or transmits data (e.g., a communication system) is at risk of such errors.
Coding techniques were therefore developed to facilitate detection, and in some cases correction, of data errors. One such coding technique adds parity bits to the data before it is stored or transmitted. A device receives the data and, based on the parity bits, determines if there are errors in the data. Only errors of a particular length, such as one-bit errors, can be detected efficiently using these codes.
Coding techniques which go one step further, and correct errors in the data, require a large number of parity bits. The more parity bits that are used, however, the less storage space/bandwidth can be used for data bits.
One aspect of the invention relates to detecting and/or correcting predefined errors having various bit (1,0) combinations and lengths. In particular, a parity check matrix is generated that is used to detect the predefined errors based on parity bits in the data. A generation matrix is developed from the parity check matrix for adding the parity bits to the data.
In this aspect, values for elements in a column of the parity check matrix are selected. A predefined error is processed with the selected values in order to produce a syndrome matrix. The selected values are assigned to the column of the parity check matrix if an element of the syndrome has a value indicative of the predefined error.
By including values in the parity check matrix that produce a syndrome element indicative of the predefined error, it is possible to ensure that the parity check matrix can be used detect that error. Doing this for each error in a list of predefined errors produces a parity check matrix that can detect all errors in the list. This can be done for any list of errors, including errors having different lengths. Coding can be performed using a simple variant of the parity check matrix.
One or more of the following features/functions may also be included in this aspect.
Processing the predefined error with the selected value may comprise multiplying the predefined error by the selected value. If a selected element has a value that is not indicative of a predefined error, different values are selected for the elements. The different values are processed with the predefined error to produce a new syndrome, and the different values are assigned to the column of the parity check matrix if the syndrome has a value indicative of the predefined error. A new predefined error may also be selected, and the foregoing process repeated for the new predefined error.
The selecting, processing and assigning described above start at a last column of the parity check matrix and proceed, column-by-column, to a first column of the parity check matrix. The predefined error is included in an n-bit (n greater than 1) string when the predefined error is processed with the selected values. The predefined error is moved to a different location in the n-bit string when it is processed with a different column of the parity check matrix.
Values for elements in the column comprise bit combinations that are possible for the column. The values are selected for the column by selecting each possible bit combination, in turn, for processing. A generation matrix for coding strings of bits is determined from the parity check matrix. A decoder comprised of logic gates is used to generate the parity check matrix.
In another aspect of the invention, a predefined error in a coded string of bits is detected by generating a parity check matrix based on the predefined error, and processing the string with the parity check matrix to produce a syndrome having one or more elements. It is then determined if the syndrome has an element that is indicative of the predefined error.
One or more of the following features/functions may also be included in this aspect.
An element hi (ixe2x89xa71) in a column of the parity check matrix is selected such that:             h      i        ≠                  ∑                  k          =          2                          min          ⁢                      xe2x80x83                    ⁢                      (                                          l                j                            ,                              n                -                i                                      )                              ⁢              xe2x80x83            ⁢                        h                      i            +            k            -            1                          ⁢                  e          jk                ⁢                  xe2x80x83                ⁢        for        ⁢                  xe2x80x83                ⁢        1              ≤    j    ≤    M    ,
where l is a number of bits in an error, n is a number of bits in the coded string, M is a number of errors, and e is a bit in the error. A portion of the parity check matrix comprises an identity matrix.
In another aspect, a string of bits is coded to permit detection of predefined errors. A parity check matrix is generated which detects the predefined errors, and a generation matrix is determined from the parity check matrix. The string of bits is then processed with the generation matrix.
In another aspect, an error detection code (xe2x80x9cEDCxe2x80x9d) is used to correct a coded bit string. This is done by receiving data for the coded bit string, and determining distances between the data and bit combinations corresponding to the data. A bit combination is selected, to substitute for the data, that is permitted by the error detection code and that has a minimum distance. By using an EDC to perform error correction in this manner, error correction is performed with relatively few bits.
One or more of the following features/functions may also be included in this aspect. The error detection code requires that a number of bits in the coded bit string comply with a condition. The condition may be that the coded bit string have an even number of ones.
This brief summary has been provided so that the nature of the invention can be understood quickly. A detailed description of illustrative embodiments of the invention is set forth below.